/**
 * 创建图类
 */
function Graph() {
	var vertices = []; // 使用一个数组存储图中所有的顶点
	var adjList = new Dictionary(); // 字典存储邻接表，使用顶点的名字作为键，邻接顶点列表作为值
	
	/**
	 * 接收一个顶点v
	 * 将该点添加到顶点列表中
	 * 并且在邻接表中，设置顶点v作为键对应的字典值为一个空数组
	 * @param {[type]} v [description]
	 */
	this.addVertex = function(v) {
		vertices.push(v);
		adjList.set(v, []);
	}
	
	/**
	 * 接收两个顶点作为参数
	 * 通过将w加入到v的邻接表中，添加了一条从顶点v到顶点w的边
	 * 如果想实现一个有向图，只做这一步就够了
	 * 第二步添加一条从w到v的边
	 * @param {[type]} v [description]
	 * @param {[type]} w [description]
	 */
	this.addEdge = function(v, w) {
		adjList.get(v).push(w);
		adjList.get(w).push(v);
	}

	this.toString = function() {
		var s = '';
		var l = vertices.length;
		for (var i = 0; i < l; i++) {
			s += vertices[i] + ' -> ';
			var neighbors = adjList.get(vertices[i]);
			var len = neighbors.length;
			for (var j = 0; j < len; j++) {
				s += neighbors[j] + ' ';
			}
			s += '\n';
		}
		return s;
	}

	/**
	 * 广度优先算法
	 * 会从指定的第一个顶点开始遍历图
	 * 先访问其所有的相邻点，就像一次访问图的一层
	 * 换句话说就是先宽后深地访问顶点
	 * 以下是从顶点v开始的广度优先搜索算法所遵循的步骤
	 * 1. 创建一个队列Q
	 * 2. 将v标注为被发现的(灰色), 并将v入队列Q
	 * 3. 如果Q非空，则运行以下步骤:
	 *     3.1 将u从Q中出队列
	 *     3.2 将标注u为被发现的(灰色)
	 *     3.3 将u所有未被访问过的邻点(白色)入队列
	 *     3.4 将u标注为已被探索的(黑色)
	 */
	var initializeColor = function() {
		var color = [];
		for (var i = 0; i < vertices.length; i++) {
			color[vertices[i]] = 'white';
		}
		return color;
	}

	this.bfs = function(v, callback) {
		var color = initializeColor(),
		    queue = new Queue();
		queue.enqueue(v);

		while (!queue.isEmpty()) {
			var u = queue.dequeue(),
			    neighbors = adjList.get(u);
			color[u] = 'grey';
			for (var i = 0; i < neighbors.length; i++) {
				var w = neighbors[i];
				if (color[w] === 'white') {
					color[w] = 'grey';
					queue.enqueue(w);
				}
			}
			color[u] = 'black';
			if (callback) {
				callback(u);
			}
		}
	}

	function printNode(value) {
		console.log('Visited vertex: ' + value);
	}

	this.BFS = function(v) {
		var color = initializeColor(),
		    queue = new Queue(),
		    d = [],
		    pred = [];
		queue.enqueue(v);

		for (var i = 0; i < vertices.length; i++) {
			d[vertices[i]] = 0;
			pred[vertices[i]] = null;
		}

		while (!queue.isEmpty()) {
			var u = queue.dequeue(),
			    neighbors = adjList.get(u);
			for (i = 0; i < neighbors.length; i++) {
				var w = neighbors[i];
				if (color[w] === 'white') {
					color[w] = 'grey';
					d[w] = d[u] + 1;
					pred[w] = u;
					queue.enqueue(w);
				}
			}
			color[u] = 'black';
		}
		return {
			distances: d,
			predecessors: pred
		}
	}
	
	/**
	 * 深度优先搜索
	 * 1. 标注v为被发现的(灰色)。
	 * 2. 对于v的所有未访问的邻点w:
	 *     1. 访问顶点w。
	 * 3. 标注v为已被探索的(黑色)。
	 * @param  {Function} callback [description]
	 * @return {[type]}            [description]
	 */
	this.dfs = function(callback) {
		var color = initializeColor();
		for (var i = 0; i < vertices.length; i++) {
			if (color[vertices[i]] === 'white') {
				dfsVisit(vertices[i], color, callback);
			}
		}
	}

	var dfsVisit = function(u, color, callback) {
		color[u] = 'grey';
		if (callback) {
			callback(u);
		}
		var neighbors = adjList.get(u);
		for (var i = 0; i < neighbors.lenght; i++) {
			var w = neighbors[i];
			if (color[w] === 'white') {
				dfsVisit(w, color, callback);
			}
		}
		color[u] = 'black';
	}

	var time = 0;
	this.DFS = function() {
		var color = initializeColor(),
		    d = [],
		    f = [],
		    p = [],
		    l = vertices.length;
		time = 0;
		for (var i = 0; i < l; i++) {
			f[vertices[i]] = 0;
			d[vertices[i]] = 0;
			p[vertices[i]] = null;
		}
		for (i = 0; i < l; i++) {
			if (color[vertices[i]] === 'white') {
				DFSVisit(vertices[i], color, d, f, p);
			}
		}
		return {
			discovery: d,
			finished: f,
			predecessors: p
		}
	}

	var DFSVisit = function(u, color, d, f, p) {
		console.log('discovered ' + u);
		color[u] = 'grey';
		d[u] = ++time;
		var neighbors = adjList.get(u);
		for (var i = 0; i < neighbors.length; i++) {
			var w = neighbors[i];
			if (color[w] === 'white') {
				p[w] = u;
				DFSVisit(w, color, d, f, p);
			}
		}
		color[u] = 'black';
		f[u] = ++time;
		console.log('explored ' + u);
	}
}

function Dictionary(){
	var items = {};
	this.has = function(key){
		return items.hasOwnProperty(key); // return key in items;
	}
	this.set = function(key, value){
		items[key] = value;
	}
	this.remove = function(key){
		if(this.has(key)){
			delete items[key];
			return true;
		}
		return false;
	}
	this.get = function(key){
		return this.has(key) ? items[key] : undefined;
	}
	this.values = function(){
		var values = [];
		for(var key in items){
			if(this.has(key)){
				values.push(items[key]);
			}
		}
		return values;
	}
	this.keys = function(){
		var keys = [];
		for(var key in items){
			if(this.has(key)){
				keys.push(key);
			}
		}
		return keys;
	}
	this.clear = function(){
		items = {};
	}
	this.size = function(){
		return this.keys().length;
	}
	this.getItems = function(){
		return items;
	}
}

function Queue(){
  var items = []; 
  this.enqueue = function(element){
    items.push(element);
  }
  this.dequeue = function(){
    return items.shift();
  }
  this.front = function(){
    return items[0];
  }
  this.isEmpty = function(){
    return items.length === 0;
  }
  this.clear = function(){
    items = [];
  }
  this.size = function(){
    return items.length;
  }
}

function Stack() {
  var items = []; // 一个数组，用来存放栈数据

  this.push = function(element){
    items.push(element);
  }

  this.pop = function(){
    return items.pop();
  }

  this.peek = function(){
    return items[items.length - 1];
  }

  this.isEmpty = function(){
    return items.length === 0;
  }

  this.clear = function(){
    items = [];
  }

  this.size = function(){
    return items.length;
  }
}